#pragma once

#include <iostream>
#include <algorithm>
using namespace std;

template <class K>
struct BSTNode {
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;
	
	BSTNode(const K&key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template <class K>
class BSTree {
	typedef BSTNode<K> Node;
public:

	//构造
	BSTree() = default; // 显式地定义默认构造函数  

	//拷贝构造
	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		// 递归进行拷贝构造
		Node* newroot = new Node(root->_key);
		newroot->_left = Copy(root->_left);
		newroot->_right = Copy(root->_right);

		return newroot;
	}

	//赋值重载
	BSTree<K>& operator=(BSTree<K> t)
	{
		// 现代写法-> 直接调用swap
		swap(_root, t._root);
		return *this;
	}

	//析构
	~BSTree()
	{
		Destroy(_root);
		_root = nullptr;
	}


	bool Insert(const K& key) //需要找个节点保留插入节点的父节点，先找到要插入位置
	{
		if (_root == nullptr) { //根为空时直接插入
			_root = new Node(key); 
			return true;
		}
		// 定义parent是因为，在最后找到插入位置时，需要parent将节点进行连接
		Node* parent = nullptr;
		Node* cur = _root;
		
		while (cur) {
			// 插入的值比cur位置大，cur往右走
			if (cur->_key < key) {
				parent = cur;
				cur = cur->_right;
			}
			// 插入的值比cur位置小，cur往左走
			else if (cur->_key > key) {
				parent = cur;
				cur = cur->_left;
			}
			// 当插入的值和cur位置相等时，直接退出，因为二叉搜索树不允许有相同的元素
			else  return false;
		}
		//新插入节点与二叉搜索树连接
		cur = new Node(key);
		if (parent->_key < key) parent->_right = cur;
		else parent->_left = cur;
		
		return true;
	}

	bool Find(const K& key) 
	{
		Node* cur = _root;
		while (cur) {
			if (cur->_key < key) { //查找的值比cur小，往左走
				cur = cur->_right;
			}
			else if (cur->_key > key) { //查找的值比cur大，往右走
				cur = cur->_left;
			}
			else  return true;//找到就返回true
		}
		return false; //找不到
	}

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (cur->_key < key) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key) {
				parent = cur;
				cur = cur->_left;
			}
			else { //删除
				//子节点的左为空，0至1个孩子的情况
				if (cur->_left == nullptr) {
					if (parent == nullptr) _root = cur->_right;
					else{
						if (parent->_left == cur) parent->_left = cur->_right;

						else parent->_right = cur->_right;
					}
					//先判断该节点为父节点的左还是右
					if (parent->_left == cur)  parent->_left = cur->_right;
					else parent->_right = cur->_right;
					
					delete cur;
					return true;
				}
				//子节点的右为空
				else if (cur->_right == nullptr) {
					if (parent == nullptr) _root = cur->_left;
					else {
						if (parent->_left == cur) parent->_left = cur->_left;
						else parent->_right = cur->_left;
					}

					delete cur;
					return true;
				}
				else { //两个孩子的情况，找右子树的最小节点为替代节点
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left) {
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}
					cur->_key = rightMin->_key;
			
					if(rightMinP->_left == rightMin)  rightMinP->_left = rightMin->_right;
					else  rightMinP->_right = rightMin->_right;
					
					delete rightMin;
					return true;
				}
			}
		}
		return false;
	}
	void Inorder() //避免_root私有，无法提供的问题
	{
		_Inorder(_root);
	}
private:
	void _Inorder(Node* root)
	{
		if (root == nullptr) return;
		_Inorder(root->_left);
		printf("%d ", root->_key);
		_Inorder(root->_right);
	}

	void Destroy(Node* root)
	{
		if (root == nullptr) return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

private:
	Node* _root = nullptr;
};





namespace keyValue 
{
	template <class K, class V>
	struct BSTNode {
		//  pair<K, V> //键值对
		K _key;
		V _value;
		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;

		BSTNode(const K& key, const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};

	template <class K, class V>
	class BSTree {
		typedef BSTNode<K, V> Node;
	public:
		BSTree() = default;

		BSTree(const BSTree<K, V>& t)
		{
			_root = Copy(t._root);
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		bool Insert(const K& key, const V&value) //需要找个节点保留插入节点的父节点，先找到要插入位置
		{
			if (_root == nullptr) {
				_root = new Node(key, value); //这里需要一个构造函数
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else  return false;
			}
			cur = new Node(key, value);
			if (parent->_key < key) parent->_right = cur;
			else parent->_left = cur;

			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key) {
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					cur = cur->_left;
				}
				else  return cur;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else { //删除
					//子节点的左为空，0至1个孩子的情况
					if (cur->_left == nullptr) {
						if (parent == nullptr) _root = cur->_right;
						else {
							if (parent->_left == cur) parent->_left = cur->_right;

							else parent->_right = cur->_right;
						}
						//先判断该节点为父节点的左还是右
						if (parent->_left == cur)  parent->_left = cur->_right;
						else parent->_right = cur->_right;

						delete cur;
						return true;
					}
					//子节点的右为空
					else if (cur->_right == nullptr) {
						if (parent == nullptr) _root = cur->_left;
						else {
							if (parent->_left == cur) parent->_left = cur->_left;
							else parent->_right = cur->_left;
						}

						delete cur;
						return true;
					}
					else { //两个孩子的情况，找右子树的最小节点为替代节点
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left) {
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_key = rightMin->_key;

						if (rightMinP->_left == rightMin)  rightMinP->_left = rightMin->_right;
						else  rightMinP->_right = rightMin->_right;

						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}
		void InOrder() //避免_root私有，无法提供的问题
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}

		void Destroy(Node* root)
		{
			if (root == nullptr) return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)return nullptr;
			//递归进行拷贝构造
			Node* newRoot = new Node(root->_key, root->_value);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);

			return newRoot;
		}

	private:
		Node* _root = nullptr;
	};
}